\documentclass[10pt,a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{rotating}
\usepackage{color}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{qtree}

\newtheorem{defin}{Definition}
\newtheorem{ex}{Example}

% Draws a cylinder with "DB" in the middle
\newsavebox{\DB}
\savebox{\DB}{
\qbezier(0,30)(15,25)(30,30)
\qbezier(0,30)(15,35)(30,30)
\qbezier(0,5)(15,0)(30,5)
\put(0,5){\line(0,1){25}}
\put(30,5){\line(0,1){25}}
\put(6,12){\large DB}
}

% Draws a small stick figure
\newsavebox{\stickman}
\savebox{\stickman}{
\put(5,20){\circle{8}}
\put(5,16){\line(0,-1){12}}
\put(0,13){\line(1,0){10}}
}

% For drawing the box around nodes at the end of Section 2
\newsavebox{\nodeBox}
\savebox{\nodeBox}{
\put(0,0){\line(0,1){50}}
\put(0,0){\line(1,0){30}}
\put(30,50){\line(-1,0){30}}
\put(30,50){\line(0,-1){50}}
}

%--- Vacuum cleaner ---------------------------------------------%

% Draws the little vacuum cleaner. Dimensions: 28x20
\newsavebox{\vacuum}
\savebox{\vacuum}{
\setlength{\unitlength}{0.15mm}
\qbezier(20,10)(24,20)(28,10)
\put(20,10){\line(0,-1){7}}
\put(28,10){\line(0,-1){7}}
\put(22,2){\circle{4}}
\put(26,2){\circle{4}}
\qbezier(9,5)(15,6)(20,8)
\qbezier(5,5)(14,8)(20,10)
\put(0,1){\framebox(15,3)}
}

% Draws dirt for the vacuum cleaner. Dimensions: 11x9
\newsavebox{\dirt}
\setlength{\unitlength}{0.15mm}
\savebox{\dirt}{
\thicklines
\put(2,2){\circle{4}}
\put(5,3){\circle{4}}
\put(9,2){\circle{3}}
\put(4,6){\circle{5}}
\put(8,5){\circle{4}}
}

% Various boxes for the vacuum cleaner, with/without dirt. Dimensions: 32x33
\newsavebox{\vacVD}
\newsavebox{\vacV}
\newsavebox{\vacD}
\newsavebox{\vac}
\savebox{\vac}{
\put(0,0){\framebox(32,33)}
}
\savebox{\vacV}{
\put(0,0){\usebox{\vac}}
\put(2,14){\usebox{\vacuum}}
}
\savebox{\vacD}{
\put(0,0){\usebox{\vac}}
\put(4,2){\usebox{\dirt}}
}
\savebox{\vacVD}{
\put(0,0){\usebox{\vac}}
\put(2,14){\usebox{\vacuum}}
\put(4,2){\usebox{\dirt}}
}

% The 8 possible states for the vacuum cleaner world.
\newsavebox{\vacone}
\newsavebox{\vactwo}
\newsavebox{\vacthree}
\newsavebox{\vacfour}
\newsavebox{\vacfive}
\newsavebox{\vacsix}
\newsavebox{\vacseven}
\newsavebox{\vaceight}
\savebox{\vacone}{
\put(0,9){1}
\put(15,0){\usebox{\vacVD}}
\put(48,0){\usebox{\vacD}}
}
\savebox{\vactwo}{
\put(0,9){2}
\put(15,0){\usebox{\vacD}}
\put(48,0){\usebox{\vacVD}}
}
\savebox{\vacthree}{
\put(0,9){3}
\put(15,0){\usebox{\vacVD}}
\put(48,0){\usebox{\vac}}
}
\savebox{\vacfour}{
\put(0,9){4}
\put(15,0){\usebox{\vacD}}
\put(48,0){\usebox{\vacV}}
}
\savebox{\vacfive}{
\put(0,9){5}
\put(15,0){\usebox{\vacV}}
\put(48,0){\usebox{\vacD}}
}
\savebox{\vacsix}{
\put(0,9){6}
\put(15,0){\usebox{\vac}}
\put(48,0){\usebox{\vacVD}}
}
\savebox{\vacseven}{
\put(0,9){7}
\put(15,0){\usebox{\vacV}}
\put(48,0){\usebox{\vac}}
}
\savebox{\vaceight}{
\put(0,9){8}
\put(15,0){\usebox{\vac}}
\put(48,0){\usebox{\vacV}}
}
% For nothing
\newsavebox{\vacempty}
\savebox{\vacempty}{}

% Boxes to hold multiple belief states
\newcommand{\vacBoxEight}{
\framebox(120,60){
\put(-57,40){\usebox{\vacone}}
\put(-17,40){\usebox{\vactwo}}
\put(23,40){\usebox{\vacthree}}
\put(-57,20){\usebox{\vacfour}}
\put(-17,20){\usebox{\vacfive}}
\put(23,20){\usebox{\vacsix}}
\put(-57,0){\usebox{\vacseven}}
\put(-17,0){\usebox{\vaceight}}
}}
\newcommand{\vacBoxFour}[4]{
\framebox(80,40){
\put(-37,20){\usebox{#1}}
\put(3,20){\usebox{#2}}
\put(-37,0){\usebox{#3}}
\put(3,0){\usebox{#4}}
}}
\newcommand{\vacBoxTwo}[2]{
\framebox(40,40){
\put(-17,20){\usebox{#1}}
\put(-17,0){\usebox{#2}}
}}
\newcommand{\vacBoxOne}[1]{
\framebox(40,20){
\put(-17,0){\usebox{#1}}
}}

\setlength{\unitlength}{1pt}


% Draws a rainy-sunny diagram
\newsavebox{\rainySunnyBox}
\savebox{\rainySunnyBox}{
\thicklines

\put(20,20){R}
\put(24,23){\circle{17}}

\put(60,20){S}
\put(64,23){\circle{17}}

\put(19,30){\line(-1,0){14}}
\put(5,30){\line(0,-1){14}}
\put(5,16){\vector(1,0){14}}
\put(6,32){0.6}

\put(31,28){\vector(1,0){27}}
\put(38,30){0.4}
\put(58,18){\vector(-1,0){28}}
\put(40,9){0.2}

\put(69,30){\line(1,0){13}}
\put(82,30){\line(0,-1){14}}
\put(82,16){\vector(-1,0){14}}
\put(70,32){0.8}
}


% Simple savebox for a scheduling node
\newcommand{\schedulingNode}[3] {
\framebox(15,36){
\put(-4,-16){#3}
\put(-4,-5){#2}
\put(-4,6){#1}
}
}


% Makes a list with no extra space between the lines.
\newenvironment{itemize_packed}{
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
}{\end{itemize}}

\title{Notes for Introduction to Artificial Intelligence}
\begin{document}

%===============================================================================

\part{Welcome to AI}

\begin{defin}[Intelligent Agent]
An \emph{\textbf{Intelligent Agent}} observes the environment using its \emph{\textbf{sensors}}, makes a decision, and affects the environment using its \emph{\textbf{actuators}}.
\end{defin}

\begin{center}
\begin{picture}(200,100)
\thicklines
\put(20,20){\line(1,0){70}}
\put(90,20){\line(0,1){70}}
\put(20,20){\line(0,1){70}}
\put(20,90){\line(1,0){70}}
\put(40,92){Agent}
\put(170,55){\oval(40,90)}
\put(167,88){\begin{rotate}{-90}\large{Environment}\end{rotate}}
\put(158,90){\vector(-4,-1){80}}
\put(80,40){\vector(4,-1){80}}
\put(100,80){\begin{rotate}{15}Sensors\end{rotate}}
\put(100,40){\begin{rotate}{-15}Actuators\end{rotate}}
\color{red}
\put(65,70){\vector(0,-1){30}}
\put(50,50){\LARGE{\textbf{?}}}
\end{picture}
\end{center}


\begin{defin}[Perception-Action Cycle]
The cycle \[\emph{environment} \rightarrow \emph{sensor} \rightarrow \emph{decision} \rightarrow \emph{action} \rightarrow \emph{environment} \dots\]
\end{defin}

\section{Applications of Intelligent Agents} %------------------------------------------------

\begin{itemize_packed}

\item \textbf{Finance}
\begin{itemize}
\item The environment is the market.
\item The sensors indicate the prices.
\item The actuators make trades.
\end{itemize}

\item \textbf{Robotics}
\begin{itemize}
\item The environment is the physical world.
\item The sensors are cameras, microphones, tactile sensors, etc.
\item The actuators are motors, wheels, speakers, etc.
\end{itemize}

\item \textbf{Games}
\begin{enumerate}
\item Chess
\begin{itemize}
\item The environment is the other player (i.e., you).
\item The sensors indicate your moves.
\item The actuators are the robot's moves.
\end{itemize}
\item Video games: the goal is to make the computer player seem "real."
\end{enumerate}

\item \textbf{Medicine}
\newline Called a "Diagnostic Agent." Takes data (the symptoms) from the patient, but gives its analysis to the doctor.

\item \textbf{The World Wide Web}
\newline A Webcrawler.

\begin{center}
\begin{picture}(200,100)
\thicklines
\put(20,20){\line(1,0){70}}
\put(90,20){\line(0,1){70}}
\put(20,20){\line(0,1){70}}
\put(20,90){\line(1,0){70}}
\put(38,92){Crawler}
\put(170,55){\oval(40,90)}
\put(167,74){\begin{rotate}{-90}\large{WWW}\end{rotate}}
\put(158,90){\vector(-4,-1){80}}
\put(100,80){\begin{rotate}{15}Web pages\end{rotate}}

\put(30,40){\usebox{\DB}}
\put(120,0){\usebox{\stickman}}

\put(80,40){\vector(2,-1){30}}
\put(110,10){\vector(-2,1){30}}
\put(80,14){\begin{rotate}{-30}Query\end{rotate}}
\end{picture}
\end{center}

\end{itemize_packed}

\section{Attributes of Environments} % -------------------------------------------------------

\begin{defin}[Fully Observable vs. Partially Observable]
An environment is \emph{\textbf{fully observable}} if the agent can sense enough data at any time to make the optimal decision. It is \emph{\textbf{partially observable}} if not enough information is immediately detectable (via the sensors) to make the optimal decision.
\end{defin}

\textbf{Example:} In poker, not all of the cards are visible. The agent must use memory and/or logic to attempt to guess them.

\begin{defin}[Deterministic vs. Stochastic]
An environment is \emph{\textbf{deterministic}} if the agent's actions uniquely determine the outcome. It is \emph{\textbf{stochastic}} if the outcome of an action is not totally predictable.
\end{defin}

\textbf{Example:} Throwing dice is stochastic, because it involves randomness.

\begin{defin}[Discrete vs. Continuous]
An environment is \emph{\textbf{discrete}} if there are finitely-many action choices, and finitely-many things that can be sensed. It is \emph{\textbf{continuous}} if there are infinitely-many.
\end{defin}

\begin{defin}[Benign vs. Adversarial]
An environment is \emph{\textbf{benign}} if the environment has no objective that would contradict that of the agent. It is \emph{\textbf{adversarial}} if the environment counteracts what the agent is trying to achieve.
\end{defin}

\textbf{Example:} The weather is benign. Chess is adversarial.

%===============================================================================

\part{Problem Solving}

\begin{defin}[Problem]
A problem is defined by the following functions, defined on the sets \textbf{S} of all possible states and \textbf{A} of all possible actions:
\begin{itemize_packed}
\item \emph{Actions} : \textbf{S} $\rightarrow$ \textbf{A} gives all possible actions at the given state.
\item \emph{Result} : (\textbf{S} $\times$ \textbf{A}) $\rightarrow$ \textbf{S} gives the resulting state of applying an action to the given state.
\item \emph{GoalTest} : \textbf{S} $\rightarrow$ \emph{\{true, false\}} indicates if a given state is a goal.
\item \emph{PathCost} : ($s_1\xrightarrow{a_1}s_2\xrightarrow{a_2}s_3$...) $\rightarrow$ $\mathbb{Z}$ indicates the cost of a series of actions. Note that if \emph{PathCost} is additive, then it can be defined simply by \emph{StepCost} : (\textbf{S} $\times$ \textbf{A}) $\rightarrow$ $\mathbb{Z}$, which gives the cost for a single action.
\end{itemize_packed}
\end{defin}

\begin{defin}[Frontier]
The farthest parts that have been \emph{explored} (but not visited!).
\end{defin}

\section{Search algorithms} %-----------------------------------------------------------------

The following algorithm will be studied in this chapter:

\begin{algorithm}
\caption{TreeSearch}
\begin{algorithmic}[1]
\REQUIRE problem
\ENSURE TreeSearch = (Path to goal) or (fail)
\STATE frontier = \{[initial state]\}
\LOOP
	\IF{frontier is empty}
		\RETURN fail
	\ENDIF
	\STATE \label{remove_choice} path = remove\_choice(frontier)
	\STATE s = path.end
	\IF{GoalTest(s)}
		\RETURN path
	\ENDIF
	\FOR{a in Actions(s)}
		\STATE \label{addResult} add Result(s,a) to frontier
	\ENDFOR
\ENDLOOP
\end{algorithmic}
\end{algorithm}

Before going further, an optimization is immediately apparent. The \textbf{GraphSearch} algorithm improves on \textbf{TreeSearch} by eliminating redundant paths (i.e., backtracking). It modifies TreeSearch in the following ways:
\begin{itemize_packed}
\item An extra variable, \emph{explored}, maintains a set of all nodes visited.
\item After calling \emph{remove\_choice} on line \ref{remove_choice}, add \emph{s} to \emph{explored}
\item In the \textbf{for}-loop, do not execute line \ref{addResult} if $Result(s,a) \in explored$ or $frontier$
\end{itemize_packed}

Different choices for how to define the \emph{remove\_choice} function produce different ways to search the tree. We have:

\begin{defin}[Breadth-first search]
\emph{remove\_choice} always returns the state with the \underline{shortest path}.
\end{defin}

\begin{defin}[Uniform-cost aka "cheapest-first" search]
\emph{remove\_choice} always returns the state with the \underline{lowest total cost}.
\end{defin}

\begin{defin}[Depth-first search]
\emph{remove\_choice} always returns the state with the \underline{longest path}.
\end{defin}

Note that:

\begin{itemize_packed}
\item Breadth-first search is optimal, in that it always finds the \textbf{shortest path}.
\item Uniform-cost search is optimal, in that it always finds the \textbf{cheapest path} (assuming that all step costs are strictly positive).
\item Depth-first search is not optimal, but has the advantage of needing less storage space than the others.
\end{itemize_packed}

\begin{defin}[complete]
A \emph{complete} algorithm will always find a solution.
\end{defin}

To improve on the preceding search algorithms, more information is needed. Suppose we have available a heuristic function $h$ : \textbf{S}$\rightarrow\mathbb{R}^+$ that estimates the distance from any state to the goal.

\begin{defin}[Greedy best-first search]
\emph{remove\_choice} always returns the state \underline{closest to the goal}.
\end{defin}

\begin{defin}[A* search]
\emph{remove\_choice} always returns the state with the \underline{minimum value of $f$}. The function $f$ is defined as $f = g + h$, where $g = PathCost$.
\end{defin}

The A* algorithm will find the lowest-cost path \textbf{IF} the distance function $h$ satisfies the condition:
\begin{center}
$h(s)$ $\leq$ the true cost from $s$.
\end{center}
In this case, we say that $h$
\begin{itemize_packed}
\item never over-estimates
\item is \textbf{optimistic}
\item is \textbf{admissible}
\end{itemize_packed}

An admissible heuristic can be derived from a formal statement of a problem by relaxing one or more of the constraints.

\section{Summary} %-----------------------------------------------------------

The techniques of problem-solving discussed in this chapter can be applied when the problem being studied is:
\begin{itemize_packed}
\item fully observable
\item discrete
\item deterministic
\item static (i.e., only the agent can change the state of the environment)
\item the set of all possible actions at any given state is known.
\end{itemize_packed}

\section{A note on implementation} %----------------------------------------------------------

A state is implemented on a computer as a data structure called a \textbf{node}. A node consists of four fields:
\begin{itemize_packed}
\item \textbf{State}: a description of the state of the environment at the end of the path.
\item \textbf{Action}: the action taken to arrive at that state.
\item \textbf{Cost}: the total cost of getting to that state.
\item \textbf{Parent}: a pointer to the previous node in the path
\end{itemize_packed}

\noindent\textbf{Example}: Suppose we have the path
\begin{center}
$A \rightarrow S \rightarrow F$.
\end{center}
This would be implemented with the following nodes:

\begin{center}
\begin{picture}(250,100)
\thicklines

\put(3,49){\textbf{state}}
\put(3,37){\textbf{action}}
\put(3,25){\textbf{cost}}
\put(3,13){\textbf{parent}}

\put(50,10){\usebox{\nodeBox}}
\put(53,49){A}
\put(53,37){$\emptyset$}
\put(53,25){0}
\put(53,13){$\emptyset$}

\put(130,10){\usebox{\nodeBox}}
\put(133,49){S}
\put(133,37){A$\rightarrow$S}
\put(133,25){...}
\put(133,13){A}

\put(210,10){\usebox{\nodeBox}}
\put(213,49){F}
\put(213,37){S$\rightarrow$F}
\put(213,25){...}
\put(213,13){S}

\put(212,16){\vector(-4,1){50}}
\put(132,16){\vector(-4,1){50}}

\end{picture}
\end{center}

In addition,
\begin{itemize_packed}
\item The frontier nodes are best stored as two data structures:
\begin{itemize_packed}
\item A \textbf{priority queue}, since we need to be able to dynamically add new nodes and remove the "best"
\item A \textbf{set}, since we need to be able to check membership.
\end{itemize_packed}
\item The explored nodes are best stored as a \textbf{set}, since we need to dynamically add new nodes and check membership.
\end{itemize_packed}

%===============================================================================

\part{Probability in AI}

\paragraph{Bayes Networks.} In this class, all events are assumed to be \textbf{binary}, i.e. there are only two possible values.

\noindent Consider the following diagram, representing an attempt to diagnose a car that won't start.

\begin{center}
\begin{picture}(300,200)
\thicklines

\put(20,180){Battery}
\put(25,170){Age}
\put(18,166){\framebox(37,24)}

\put(37,166){\vector(0,-1){16}}

\put(20,140){Battery}
\put(23,130){Dead}
\put(18,126){\framebox(37,24)}

\put(37,126){\vector(-1,-4){4}}
\put(39,126){\vector(3,-2){47}}

\put(10,100){Battery}
\put(12,90){Meter}
\put(8,86){\framebox(37,24)}

\put(80,180){Alternator}
\put(85,170){Broken}
\put(78,166){\framebox(49,24)}

\put(108,166){\vector(1,-2){8}}

\put(150,180){Fan belt}
\put(151,170){Broken}
\put(148,166){\framebox(41,24)}

\put(160,166){\vector(-3,-2){24}}

\put(120,140){Not}
\put(110,130){Charging}
\put(108,126){\framebox(44,24)}

\put(129,125){\vector(-2,-3){17}}

\put(90,90){Battery}
\put(94,80){Flat}
\put(88,76){\framebox(37,24)}

\put(100,75){\vector(-3,-2){75}}
\put(103,75){\vector(-1,-1){43}}
\put(106,75){\vector(-1,-4){11}}
\put(109,75){\vector(3,-4){33}}

\put(10,15){Lights}
\put(8,11){\framebox(30,14)}

\put(50,20){Oil}
\put(48,10){Light}
\put(46,6){\framebox(28,24)}

\put(90,20){Gas}
\put(85,10){Gauge}
\put(83,6){\framebox(32,24)}

\put(160,80){No}
\put(159,70){Oil}
\put(157,66){\framebox(20,24)}

\put(167,65){\vector(-3,-1){100}}
\put(170,65){\vector(2,-3){27}}

\put(190,80){No}
\put(189,70){Gas}
\put(187,66){\framebox(20,24)}

\put(198,65){\vector(-3,-1){100}}
\put(200,65){\vector(-3,-2){50}}
\put(202,65){\vector(1,-4){10}}

\put(215,80){Fuel Line}
\put(216,70){Blocked}
\put(213,66){\framebox(45,24)}

\put(230,65){\vector(-2,-1){70}}

\put(267,80){Starter}
\put(267,70){Broken}
\put(265,66){\framebox(35,24)}

\put(270,65){\vector(-3,-1){100}}

\put(190,15){Dipstick}
\put(188,11){\framebox(40,14)}

\color{red}
\put(130,20){Car Won't}
\put(140,10){Start}
\put(128,6){\framebox(50,24)}

\end{picture}
\end{center}

Bayes Networks have many applications, including:
\begin{itemize_packed}
\item Diagnostics
\item Prediction
\item Machine Learning
\item Finance
\item Robotics
\item Web searching
\item Particle filters
\item HMM
\end{itemize_packed}

\paragraph{Probability} Essential to the understanding of Bayes Networks is the theory of probability.

\begin{defin}[Complementary Probability] \quad
\begin{center}
$P(A) = p \iff P(\neg A) = 1-p$
\end{center}
\end{defin}

\begin{defin}[Independence] \quad
\begin{center}
$X \perp Y \implies P(X,Y) = P(X)P(Y)$
\end{center}
\begin{itemize_packed}
\item $X \perp Y$ means $X$ is \emph{\textbf{(absolutely) independent}} of $Y$.
\item $P(X,Y)$ is the \emph{\textbf{Joint Probability}} of $X$ and $Y$.
\item $P(X)$ and $P(Y)$ are the \emph{\textbf{Marginal Probabilities}} of $X$ and $Y$.
\end{itemize_packed}
\end{defin}

\begin{defin}[Total Probability] \quad
\begin{center}
$P(Y) = \displaystyle\sum_i P(Y|X=i)P(X=i)$
\end{center}
\end{defin}

\begin{defin}[Conditional Probability] \quad
\begin{center}
$P(Q|E) = \displaystyle\frac{P(Q,E)}{P(E)}$
\end{center}
\end{defin}

\begin{defin}[Bayes' Rule] \quad
\begin{center}
$P(A|B) = \displaystyle\frac{P(B|A)P(A)}{P(B)}$
\end{center}
\begin{itemize_packed}
\item $P(A|B)$ is called the \emph{\textbf{posterior}}.
\item $P(B|A)$ is called the \emph{\textbf{likelihood}}.
\item $P(A)$ is called the \emph{\textbf{prior}}.
\item $P(B)$ is called the \emph{\textbf{marginal likelihood}}.
\end{itemize_packed}
The marginal likelihood is often expanded using the total probability.
\end{defin}

\begin{defin}[Diagnostic Reasoning] A Bayes Network often has the following form:
\begin{center}
\begin{picture}(90,70)
\thicklines
\put(0,0){\framebox(90,70)}

\put(10,10){B}
\put(14,13){\circle{17}}
\put(28,10){observable}

\put(10,50){A}
\put(27,50){not observable}
\put(15,53){\circle{17}}

\put(14,46){\vector(0,-1){25}}
\end{picture}
\end{center}

\noindent where $P(A)$, $P(B|A)$ and $P(B|\neg A)$ are known. \emph{\textbf{Diagnostic Reasoning}} is the process by which we attempt to find $P(A|B)$ or $P(A|\neg B)$.
\end{defin}

\begin{defin}[Conditional Independence] The variables $A$ and $B$ are \emph{\textbf{Conditionally Independent given $C$}} if
\begin{center}
$P(A|C,B) = P(A|C)$.
\end{center}
\noindent In this case, we write $A \perp B \; | \; C$.
\end{defin}

\paragraph{Conditional versus Absolute Independence.} Consider the following two examples:
\begin{center}
\begin{picture}(170,90)
\thicklines

\put(10,20){$T_1$}
\put(15,23){\circle{17}}

\put(50,20){$T_2$}
\put(55,23){\circle{17}}

\put(30,60){$C$}
\put(34,63){\circle{17}}

\put(31,55){\vector(-1,-2){12}}
\put(37,55){\vector(1,-2){12}}

\put(11,1){$T_1 \perp T_2 \; | \; C$}


\put(110,60){$S$}
\put(115,63){\circle{17}}

\put(150,60){$R$}
\put(155,63){\circle{17}}

\put(130,20){$H$}
\put(135,23){\circle{17}}

\put(117,55){\vector(1,-2){12}}
\put(153,55){\vector(-1,-2){12}}

\put(122,1){$S \perp R$}

\end{picture}
\end{center}

\noindent The network on the left represents two tests, $T_1$ and $T_2$, used to determine whether a patient has cancer, represented by $C$. The tests $T_1$ and $T_2$ are conditionally independent given $C$: if we already know whether the person has cancer, then knowing the outcome of one test will have no effect on the probability of the other test. However, $T_1$ and $T_2$ are \textbf{not} absolutely independent. If we do not know whether the patient has cancer, then a positive (or negative) result on one test will affect the probability of the other test.

In the network on the right, $S$ represents whether it is sunny outside, $R$ represents whether the professor got a raise, and $H$ represents whether the professor is happy. In this example, $S$ and $R$ are absolutely independent: the weather and the professor's salary have nothing to do with each other. However, $S$ and $R$ are \textbf{not} conditionally independent given $H$. If we know that the professor is happy, then sunny weather could "\textbf{explain away}" his happiness, making a raise less likely.

\paragraph{Advantages of Bayes Networks.} \quad

\begin{picture}(300,100)
\thicklines

\put(5,85){A}
\put(9,88){\circle{17}}

\put(12,80){\vector(2,-3){13}}

\put(45,85){B}
\put(49,88){\circle{17}}

\put(46,80){\vector(-2,-3){13}}

\put(25,50){C}
\put(29,53){\circle{17}}

\put(26,45){\vector(-2,-3){13}}
\put(32,45){\vector(2,-3){13}}

\put(5,15){D}
\put(9,18){\circle{17}}

\put(45,15){E}
\put(49,18){\circle{17}}

\put(80,40){
\begin{tabular}{r l}
Given: & $P(A) \quad P(B)$ \\
 & $P(C|A,B)$ \\
 & $P(D|C) \quad P(E|C)$ \\
Find: & $P(A,B,C,D,E)$ \\
 & $=P(A)P(B)P(C|A,B)P(D|C)P(E|C)$
\end{tabular}
}
\end{picture}

\noindent The advantage of using a Bayes Network to describe this situation, is that calculating $P(A,B,C,D,E)$ only requires 10 variables. Enumerating all the possibilities would require storing $2^5-1 = 31$ different values.

In general, if a node has $k$ incoming arcs, it will require $2^k$ variables.

\paragraph{D-separation, aka Reachability.}

\begin{center}
\begin{picture}(100,50)
\put(10,25){\circle*{17}}
\put(20,22){ = known variable's value}
\end{picture}
\end{center}

\begin{center}
\begin{picture}(260,60)
\thicklines

\put(20,50){\underline{Active Triplets}}
\put(160,50){\underline{Inactive Triplets}}

\put(10,10){\circle{17}}
\put(18,10){\vector(1,0){24}}
\put(50,10){\circle{17}}
\put(58,10){\vector(1,0){24}}
\put(90,10){\circle{17}}

\put(160,10){\circle{17}}
\put(168,10){\vector(1,0){24}}
\put(200,10){\circle*{17}}
\put(208,10){\vector(1,0){24}}
\put(240,10){\circle{17}}

\end{picture}
\end{center}

\begin{center}
\begin{picture}(260,70)
\thicklines

\put(50,53){\circle{17}}
\put(30,18){\circle{17}}
\put(70,18){\circle{17}}

\put(47,45){\vector(-2,-3){13}}
\put(53,45){\vector(2,-3){13}}

\put(200,53){\circle*{17}}
\put(180,18){\circle{17}}
\put(220,18){\circle{17}}

\put(197,45){\vector(-2,-3){13}}
\put(203,45){\vector(2,-3){13}}

\end{picture}
\end{center}

\begin{center}
\begin{picture}(260,60)
\thicklines

\put(30,48){\circle{17}}
\put(70,48){\circle{17}}
\put(50,13){\circle*{17}}

\put(33,40){\vector(2,-3){13}}
\put(67,40){\vector(-2,-3){13}}

\put(180,48){\circle{17}}
\put(220,48){\circle{17}}
\put(200,13){\circle{17}}

\put(183,40){\vector(2,-3){13}}
\put(217,40){\vector(-2,-3){13}}

\end{picture}
\end{center}

\begin{center}
\begin{picture}(260,110)
\thicklines

\put(30,98){\circle{17}}
\put(70,98){\circle{17}}
\put(50,63){\circle{17}}

\put(33,90){\vector(2,-3){13}}
\put(67,90){\vector(-2,-3){13}}
\put(50,55){\vector(0,-1){20}}

\put(50,31){\circle*{1}}
\put(50,27){\circle*{1}}
\put(50,23){\circle*{1}}

\put(50,12){\circle*{17}}

\end{picture}
\end{center}

%===============================================================================

\part{Probabilistic Inference}

Consider the following Bayes network:

\begin{center}
\begin{picture}(150,100)
\thicklines

\put(5,85){B}
\put(9,88){\circle{17}}

\put(12,80){\vector(2,-3){13}}

\put(45,85){E}
\put(49,88){\circle{17}}

\put(46,80){\vector(-2,-3){13}}

\put(25,50){A}
\put(29,53){\circle{17}}

\put(26,45){\vector(-2,-3){13}}
\put(32,45){\vector(2,-3){13}}

\put(5,15){J}
\put(9,18){\circle{17}}

\put(45,15){M}
\put(49,18){\circle{17}}

\put(80,80){B = burglary}
\put(80,65){E = earthquake}
\put(80,50){A = alarm went off}
\put(80,35){J = John was called}
\put(80,20){M = Mary was called}
\end{picture}
\end{center}

\noindent Typically, a computer function would take B and E as the input, and calculate J and M as the output. In this case,

\begin{tabular}{r@{ } @{}c@{} @{ }l l}
B and E & are called the & \textbf{evidence} & (known) \\
J and M & are called the & \textbf{query} & (desired) \\
A & is & \textbf{hidden} & (required for computations)
\end{tabular}

\begin{defin}[Posterior Distribution]
$P(Q_1,Q_2,...|E_1=e_1, E_2=e_2, ...)$. The variables $Q_i$ are called the \emph{\textbf{query variables}}, and the $E_j$ are called the \emph{\textbf{evidence variables}}.
\end{defin}

We define
\begin{center}
$argmax_q P(Q_1=q_1, ... | E_1=e_1, ...)$
\end{center}
\noindent to be the combination of values with the highest probability.

\paragraph{Enumeration.} We start with the question, what is $P(+b | +j, +m)$? From the formula for conditional probability, this is equivalent to
\begin{center}
$\displaystyle\frac{P(+b,+j,+m)}{P(+j,+m)}$
\end{center}
\noindent We then enumerate the atomic probabilities, and calculate the sum of the products.
\begin{center}
\begin{align*}
P(+b,+j,+m) & = \sum_e\sum_aP(+b,+j,+m) \\
 & = \sum_e\sum_a\underbrace{P(+b)P(e)P(a|+b,e)P(+j|a)P(+m|a)}_{f(e,a)} \\
 & = f(+e,+a) + f(+e,\neg a) + f(\neg e,+a) + f(\neg e, \neg a).
\end{align*}
\end{center}
\noindent The problem with this method is that it quickly becomes impractical for even moderately-sized networks. $f$ can be optimized somewhat:
\begin{center}
$\displaystyle f(e,a) = P(+b)\sum_eP(e)\sum_aP(a|+b,e)P(+j|a)P(+m|a)$
\end{center}
\noindent but this is not sufficient.

\paragraph{Maximizing independence.} Consider the following networks:

\begin{center}
\begin{picture}(250,100)
\thicklines
\put(35,90){\underline{Network}}
\put(150,90){\underline{Time to compute}}

\put(10,70){$x_1$}
\put(15,72){\circle{17}}

\put(23,72){\line(1,0){13}}

\put(40,70){$x_2$}
\put(45,72){\circle{17}}

\put(53,72){\line(1,0){13}}

\put(70,70){\dots}

\put(83,72){\line(1,0){13}}

\put(100,70){$x_n$}
\put(105,72){\circle{17}}

\put(180,70){$O(n)$}


\put(10,20){$x_1$}
\put(15,22){\circle{17}}

\put(23,22){\line(1,0){13}}
\qbezier(21,28)(30,32)(38,28)
\qbezier(20,30)(50,40)(72,26)
\qbezier(18,31)(60,50)(98,28)

\put(40,20){$x_2$}
\put(45,22){\circle{17}}

\put(53,22){\line(1,0){13}}
\qbezier(51,17)(60,12)(72,17)
\qbezier(49,15)(75,0)(99,16)

\put(70,20){\dots}

\put(83,22){\line(1,0){13}}
\qbezier(76,17)(86,10)(97,18)

\put(100,20){$x_n$}
\put(105,22){\circle{17}}

\put(180,20){$O(2^n)$}

\end{picture}
\end{center}

\noindent In the first network, there is only one edge between each node. In the second, every node has an edge with every other node. This gives us bounds for best- and worst-case run-time.

Bayes networks are the easiest to use when they are directed in the \textbf{causal direction}, i.e. when the network flows from causes to effects.

\paragraph{Variable elimination.} Another way to optimize $f$ that is faster than enumeration, is the following. Consider the follwing network:

\begin{center}
\begin{picture}(100,25)
\thicklines

\put(10,10){$R$}
\put(15,13){\circle{17}}

\put(23,13){\vector(1,0){13}}

\put(40,10){$T$}
\put(45,13){\circle{17}}

\put(53,13){\vector(1,0){13}}

\put(70,10){$L$}
\put(75,13){\circle{17}}

\end{picture}
\end{center}

\noindent where $R$ represents rain, $T$ represents heavy traffic, and $L$ represents the student being late to class. We know the probabilities $P(R)$, $P(T|R)$, and $P(L|T)$, for all possible values $r$, $t$, and $l$. We perform the following steps:

\begin{enumerate}
\item \textbf{Joining factors}: combine $R$ and $T$ into $P(R,T) = P(T|R)P(R)$
\item Sum over $R$ to eliminate $R$, leaving $T$:
\begin{align*}
P(+t) & = P(+t,+r) + P(+t,\neg r) \\
P(\neg t) & = P(\neg t,+r) + P(\neg t, \neg r)
\end{align*}
\item Join the factors $T$ and $L$.
\item Sum over $T$ to elimnate $T$, leaving $L$.
\end{enumerate}

%===============================================================================

\part{Machine Learning}

In previous sections, we discussed Bayes networks, which involve \underline{reasoning with known models}. Machine learning involves \underline{determining the model from the given data}. Machine learning has been used by many companies, for many reasons, including
\begin{itemize_packed}
\item \textbf{Google} for web mining
\item \textbf{Netflix} for creating DVD recommendations
\item \textbf{Amazon} for product placement
\end{itemize_packed}

\noindent Professor Thrun's team has used machine learning to win the DARPA Grand Challenge, where a car equipped with sensors was able to follow a road through rough terrain.

Machine learning can be summarized with the following points.
\begin{itemize_packed}
\item \textbf{What?}
\begin{itemize_packed}
\item parameters, e.g. the probabilities of a Bayes network
\item structure, e.g. the arcs in a Bayes network
\item hidden concepts, e.g. hidden concepts that can help interpret data
\end{itemize_packed}

\item \textbf{What from?}
\begin{itemize_packed}
\item supervised, where we are given specific target labels
\item unsupervised, where target labels are missing
\item reinforcement, where an agent tries things and gets feedback from the environment about their success
\end{itemize_packed}

\item \textbf{What for?}
\begin{itemize_packed}
\item prediction, i.e. what will happen in the future
\item diagnostics, i.e. find an explanation for the data
\item summarization, e.g. of an article
\end{itemize_packed}

\item \textbf{How}
\begin{itemize_packed}
\item passive, where the agent is an observer that does not affect the data
\item active
\item online, i.e. while the data is being generated
\item offline, i.e. after the data has been generated
\end{itemize_packed}

\item \textbf{Outputs?}
\begin{itemize_packed}
\item classification, where the output is discrete (e.g., is an object a chair)
\item regression, where the output is continuous (e.g., temperature)
\end{itemize_packed}

\item \textbf{Details?}
\begin{itemize_packed}
\item generative, which seeks to model the data as generally as possible
\item discriminative, which seeks to distinguish data
\end{itemize_packed}

\end{itemize_packed}

\section{Supervised Learning}

In supervised learning, for each training example we are given a feature vector, and a target label indicating the output for that vector.
\begin{center}
$x_1 x_2 \dots x_n \rightarrow y$
\end{center}
For example, the $x_i$ might indicate if a person is employed, their salary, if they have previously defaulted, etc., and $y$ predicts if the person will default on a new line of credit. The goal is to produce a function that will predict the correct value of $y$ for future customers. Typically, we are given several examples:
\begin{center}
$\begin{bmatrix}
x_{11} & x_{12} & \dots & x_{1N} & \rightarrow & y_1 \\
x_{21} & x_{22} & \dots & x_{2N} & \rightarrow & y_2 \\
\vdots & & & & & \vdots \\
x_{M1} & x_{M2} & \dots & x_{MN} & \rightarrow & y_M
\end{bmatrix}$
data
\end{center}
where the vector $\left(x_{i1}, \dots, x_{iN}\right)$ can be represented simply by $x_i$. The goal is to find a function $f$ that, for any future vector $x_m$, will give a value $y_m$ with minimal error.
\begin{center}
$f(x_m) = y_m$
\end{center}

\section{Spam detection}

The goal of spam detection is to determine if an e-mail is \textbf{spam} (junk) or \textbf{ham} (acceptable). One simple way to represent e-mails is with a bag of words. A \textbf{bag of words} is a map that maintains, for each word in the dictionary, a count of the number of occurrences of that word in the data.

\paragraph{Example:} Suppose we have the following data:
\begin{center}
\begin{tabular}{l l}
\quad \underline{SPAM} & \quad \underline{HAM} \\
offer is secret & play sports today \\
click secret link & went play sports \\
secret sports link & secret sports event \\
 & sport is today \\
 & sport costs money
\end{tabular}
\end{center}
The dictionary for this example contains 12 words. With this data, we can calculate the probability that a new message will be spam to be $\frac{3}{8}$ using maximum likelihood.

\section{Maximum Likelihood}

In the previous example, our data could be represented as
\begin{center}
$SSSHHHHH$.
\end{center}
We wish to discover the value for the prior probability $p(S) = \pi$ that a message is spam, that maximizes the probability of seeing our data (assuming each e-mail is drawn independently according to an identical distribution). In other words, we want
\begin{center}
$p(y_i) =
\begin{cases}
\pi & \text{if } y_i = S \\
1 - \pi & \text{if } y_i = H
\end{cases}$
\end{center}
If we re-write our data as $11100000$, then we could write
\begin{center}
$p(y_i) = \pi^{y_i} (1-\pi)^{1 - y_i}$
\end{center}
Assuming independence, we then have
\begin{center}
$p(data) = \displaystyle\prod_{i=1}^8 p(y_i) = \pi^{count(y_i=1)}(1-\pi)^{count(y_i = 0)} = \pi^3(1-\pi)^5$
\end{center}
Maximizing $p(data)$ is equivalent to maximizing the logarithm of $p(data)$; thus, we calculate
\begin{center}
$\log_p(data) = 3\log\pi + 5\log(1-\pi)$
\end{center}
The maximum is attained when the derivative is zero. We may thus calculate
\begin{center}
\begin{align*}
\displaystyle\frac{\mathrm{d}\log p(data)}{\mathrm{d}\pi} & = 0 \\
\frac{3}{\pi} - \frac{5}{1-\pi} & = 0 \\
\frac{3}{\pi} & = \frac{5}{1-\pi} \\
5\pi + 3\pi & = 3 \\
\pi & = \frac{3}{8}
\end{align*}
\end{center}

%===============================================================================

\part{Unsupervised Learning}

%===============================================================================

\part{Representation with Logic}

\section{Propositional Logic}

Suppose we have the symbols $B$, $E$, $A$, $M$, and $J$, representing the events from the burglary example. As in the probabilistic models, they can be true or false. However, when representing with logic, our belief in what the values are, is either true, false, or unknown. We express these beliefs using logical sentences. For example, we could write
\begin{center}
$(E\lor B)\implies A$
\end{center}
to mean, "whenever there is an earthquake or a burglary, then the alarm goes off." We could also write
\begin{center}
$A \implies (J\land M)$
\end{center}
to mean, "if the alarm goes off, then both John and Mary will call."

Using propositional logic, a model of the world is a set of truth values for the variables. For example,
\begin{center}
$\left\{E = true, B = false, ...\right\}$.
\end{center}
A \textbf{truth table} can be used to list all values for all our logical statements. For example,
\begin{center}
\begin{tabular}{| c | c || c | c | c | c | c |}
\hline
$P$ & $Q$ &  $\neg P$ & $P\land Q$ & $P\lor Q$ & $P\Rightarrow Q$ & $P\Leftrightarrow Q$\\
\hline
false & false & true & false & false & true & true \\
false & true & true & false & true & true & false \\
true & false & false & false & true & false & false \\
true & true & false & true & true & true & true \\
\hline
\end{tabular}
\end{center}

\begin{defin}[Valid]
A \emph{\textbf{valid}} sentence is one that is true in every possible model, for every combination of values of the propositional symbols.
\end{defin}

\begin{defin}[Satisfiable]
A \emph{\textbf{satisfiable}} sentence is one that is true in \underline{some} (but not necessarily all) models. A sentence that is false for all models is \emph{\textbf{unsatisfiable}}.
\end{defin}

\paragraph{Examples.}
\begin{center}
\begin{tabular}{c c}
\textbf{Sentence} & \textbf{Type} \\
\hline
$P\lor\neg P$ & valid \\
$P\land\neg P$ & unsatisfiable \\
$P\lor Q\lor (P\iff Q)$ & valid \\
$(P\Rightarrow Q) \lor (Q\Rightarrow P)$ & valid \\
$\big((food\Rightarrow party)\lor (drinks\Rightarrow party)\big) \Rightarrow ((food\land drinks)\Rightarrow party)$ & valid
\end{tabular}
\end{center}

\paragraph{Limitations of propositional logic.}
\begin{itemize_packed}
\item It is not capable of handling uncertainty.
\item It can only handle events that are true or false; no objects, properties of objects, etc.
\item There are no "shortcuts." For example, if we wish to model a vacuum cleaner and say that 1000 locations are all clean, we would need a conjunction including all 1000 locations.
\end{itemize_packed}
First-order logic addresses the last two limitations.

\section{First-order logic}

The differences between the three main types of logic we have seen are summarized in the following table.
\begin{center}
\begin{tabular}{l | c | c |}
\cline{2-3}
& World & Beliefs \\
& (Ontology) & (Epistemology) \\
\hline
\multicolumn{1}{|l|}{First-order logic} & Relationships, Objects, Functions & \multirow{2}{*}{True/False/Unknown} \\
\cline{1-2}
\multicolumn{1}{|l|}{Propositional Logic} & \multirow{2}{*}{Facts} & \\
\cline{1-1} \cline{3-3}
\multicolumn{1}{|l|}{Probability Theory} & & $[0,1]$ \\
\hline
\end{tabular}
\end{center}

There are three main ways to represent the world.
\begin{itemize_packed}
\item An \textbf{atomic} representation considers the world to be a single object, without attempting to represent its internal structure. This is the representation that was used for search and problem solving: we considered the world to be a single state, about which we knew some basic information (like whether a state was a goal), but without knowing any of the states' internal structure.
\item A \textbf{factored} representation represents a single world-state as several variables.
\item A \textbf{structured} representation considers a state to be not simply a set of values of different variables, but can also include relationships between objects, branching structures, etc. Databases and programming languages are two examples.
\end{itemize_packed}

Consider the following example:
\begin{center}
\begin{picture}(50,40)
\put(0,5){\fbox{$B_3$}}
\put(30,5){\fbox{$D_2$}}
\put(0,30){\fbox{$A_1$}}
\put(30,30){\fbox{$C_3$}}
\end{picture}
\end{center}
Using first-order logic, we have the following tools at our disposal:
\begin{itemize_packed}
\item \textbf{Constants}. $\{A,B,C,D,1,2,3,cee\}$. Note that it is not necessary to have a 1-1 correspondance between constants and objects; in this example, we have two constants that refer to the same letter.
\item \textbf{Functions}. For example, $numberof = \left\{A\rightarrow 1, B\rightarrow 3, C\rightarrow 3, D\rightarrow 2\right\}$.
\item \textbf{Relations}. A relation is a set of tuples for which the relation holds. Relations can be
\begin{itemize_packed}
\item \textbf{binary}, e.g. $above: \{ [A,B], [C,D] \}$
\item \textbf{unary}, e.g. $vowel: \{ [A] \}$
\item \textbf{0-ary}. In this case, the relation simply states something about the world in general, e.g. $rainy$, which could be $\{\}$ for false, or $\{[]\}$ for true.
\end{itemize_packed}
\end{itemize_packed}

\paragraph{Syntax.}
\begin{itemize_packed}
\item \textbf{Sentences} describe facts that are true or false (i.e. relations). For example, $vowel(A)$, $above(A,B)$, $2=2$ (note that the equality relation is always present).
\item \textbf{Operators} create new sentences by combining relations. These are the operators from propositional logic: $\land$, $lor$, $neg$, $\implies$, $\iff$, and $()$.
\item \textbf{Terms} refer to constants. They can be constants (typically in upper-case), variables (typically in lowercase), or functions.
\item \textbf{Quantifiers} are the symbols $\forall$ ("for all") and $\exists$ ("there exists"). They are used to add meaning to sentences. For example, $\forall x\quad vowel(x)\Rightarrow numberof(x) = 1$ and $\exists x\quad numberof(x)=2$. Note that, if a quantifier is omitted, "for all" is assumed.
\end{itemize_packed}

\paragraph{Examples.}
\begin{center}
\begin{tabular}{c c}
\textbf{Sentence} & \textbf{Type} \\
\hline
$\exists x,y \quad x=y$ & valid \\
$\left(\exists x \; X=x\right) \implies \left(\forall y \exists z \; y=z\right)$ & valid \\
$\forall x\quad P(x) \lor \neg P(x)$ & valid \\
$\exists x\quad P(x)$ & satisfiable
\end{tabular}
\end{center}

%===============================================================================

\part{Planning}

Previously, problem solving was used to find a path to a goal. This only works when the environment is deterministic and fully observable. In this unit, we will learn how to relax those constraints.

In certain cases, it is important to interleave steps of \textbf{planning} (i.e., looking at the current state and deciding on the path to take) and \textbf{execution}. These situations include
\begin{itemize_packed}
\item \underline{stochastic environments}, where the outcome of an action is not always guaranteed. For example, the wheels on a car might slip, or a traffic light might change color, etc.
\item \underline{multi-agent environments}, where another agent's behavior is unknown.
\item \underline{partially-observable environments}. In this case, there may be unknown obstacles that are encountered along the way.
\item an \underline{unknown model} of the world
\item \underline{hierarchical plans}. For example, the plan to drive from city A to city B does not include the low-level details of actually making the trip, such as turning the steering wheel, using the brakes, etc. These details must be addressed at execution.
\end{itemize_packed}
A solution to these problems is to plan in the space of belief states instead of world states.

\begin{defin}
When the exact state of the world is unknown, the list of all possible states is called the \emph{\textbf{belief state}}.
\end{defin}

\paragraph{Example.} Suppose we wish to model a simple world for a robotic vacuum cleaner. The world only has two positions, left and right. Each position can either have dirt, or not. The robot is in one of the two positions.

In this example, there are 8 possible world states. However, suppose the sensors on our robot are broken, and we thus know nothing about the world. We can only model our current state as a single belief state comprising all 8 possible world states. However, we can narrow down the possible world states by eliminating possibilities when an action is performed - for example, if we perform the action "move left," then we know that the robot is in the left square, thus eliminating 4 states. The following diagram illustrates the resulting belief state space.

\begin{picture}(300,280)
\thicklines

% Initial state
\put(100,190){\vacBoxEight}
\put(103,220){\vector(-1,0){19}}
\put(92,222){L}
\put(224,220){\vector(1,0){19}}
\put(230,222){R}
\put(160,190){\vector(0,-1){20}}
\put(162,177){S}


% Move L from initial
\put(0,200){\vacBoxFour{\vacone}{\vacthree}{\vacfive}{\vacseven}}
\put(70,240){\line(0,1){20}}
\put(70,260){\line(1,0){180}}
\put(250,260){\vector(0,-1){20}}
\put(72,248){R}
\put(20,200){\vector(0,-1){90}}
\put(22,140){S}

% Move R from initial
\put(240,200){\vacBoxFour{\vactwo}{\vacfour}{\vacsix}{\vaceight}}
\put(260,240){\line(0,1){30}}
\put(260,270){\line(-1,0){200}}
\put(60,270){\vector(0,-1){30}}
\put(262,248){L}
\put(310,200){\vector(0,-1){90}}
\put(312,140){S}

% Suck from initial
\put(120,130){\vacBoxFour{\vacfour}{\vacfive}{\vacseven}{\vaceight}}
\put(130,130){\vector(0,-1){20}}
\put(120,117){L}
\put(190,130){\vector(0,-1){20}}
\put(192,117){R}

% L->S
\put(0,70){\vacBoxTwo{\vacfive}{\vacseven}}
\put(10,70){\vector(0,-1){30}}
\put(0,50){R}

% S->L
\put(65,70){\vacBoxFour{\vacfive}{\vacthree}{\vacseven}{\vacempty}}
\put(67,90){\vector(-1,0){23}}
\put(55,92){S}
\put(148,80){\vector(1,0){29}}
\put(158,70){R}

% S->R
\put(175,70){\vacBoxFour{\vacsix}{\vacfour}{\vaceight}{\vacempty}}
\put(178,100){\vector(-1,0){29}}
\put(158,102){L}
\put(258,90){\vector(1,0){25}}
\put(265,92){S}

% R->S
\put(280,70){\vacBoxTwo{\vacfour}{\vaceight}}
\put(295,70){\vector(0,-1){30}}
\put(285,50){L}

% L->S->R
\put(0,0){\vacBoxTwo{\vacsix}{\vaceight}}
\put(30,40){\vector(0,1){30}}
\put(32,50){L}
\put(43,20){\vector(1,0){40}}
\put(58,22){S}

% L->S->R->S
\put(80,10){\vacBoxOne{\vaceight}}
\put(123,25){\vector(1,0){69}}
\put(157,27){L}

% R->S->L->S
\put(190,10){\vacBoxOne{\vacseven}}
\put(193,15){\vector(-1,0){69}}
\put(157,5){R}

% R->S->L
\put(280,0){\vacBoxTwo{\vacthree}{\vacseven}}
\put(315,40){\vector(0,1){30}}
\put(317,50){R}
\put(283,20){\vector(-1,0){49}}
\put(260,22){S}

\end{picture}

\noindent It is clear that, even with no sensors, it would still be possible to plan a sequence of actions that result in removing all dirt from the world.

\begin{defin}A \emph{\textbf{conformant plan}} is a plan that can find a goal without ever sensing anything about the world.
\end{defin}

\paragraph{Partially-obsevable environments.} Suppose, on the other hand, that the robot vacuum cleaner has \textbf{local} sensors, i.e., it can perceive what side it is on, and whether there is dirt there, but not whether the other square has dirt. If the world is deterministic, actions and observations will never increase the size of the belief state.

On the other hand, if the world is stochastic, an action may \textbf{increase} the size of the belief state. However, an observation will still partition the current belief state, tending to make the resulting states smaller.

For example, suppose that the vacuum cleaner's wheels might slip. We can no longer be certain of the result of moving left or right. We can still plan for this by building a tree of belief states; however, we need to introduce \textbf{branches} to account for the fact that an action might not have any result.

\begin{center}
\begin{picture}(130,30)
\thicklines
\put(0,20){\framebox(10,10)}
\put(10,25){\vector(1,0){20}}
\put(15,27){S}

\put(30,20){\framebox(10,10)}
\put(40,25){\vector(1,0){20}}
\put(45,27){R}

\put(65,25){\circle{10}}
\qbezier(65,20)(65,10)(55,15)
\put(55,15){\vector(-4,1){15}}
\put(48,5){A}
\put(70,25){\vector(1,0){20}}
\put(75,27){B}
\qbezier(65,16)(74,17)(75,25)

\put(90,20){\framebox(10,10)}
\put(100,25){\vector(1,0){20}}
\put(105,27){S}

\put(120,20){\framebox(10,10)}
\end{picture}
\end{center}
\begin{center}
plan: [S, while A:R, S]
\end{center}

%===============================================================================

\part{Planning under uncertainty}

The following table represents the subjects that will be covered:
\begin{center}
\begin{tabular}{c|c|c|}
& Deterministic & Stochastic \\
\hline
Fully & A*, Depth-first, & MDP \\
Observable & Breadth-first & \\
\hline
Partially & & POMDP \\
Observable & &\\
\hline
\end{tabular}
\end{center}

\section{Markov Decision Process (MDP)}

MDPs are generally defined using
\begin{itemize_packed}
\item states $s_1,\dots,s_N$
\item actions $a_1,\dots,a_K$
\item a state transition matrix $T(s,a,s') = P(s'|a,s)$ giving the probability of an outcome for a given action from a given state
\item a reward function $R(s)$ which serves to provide a "goal" for the MDP
\end{itemize_packed}

\paragraph{Example.} Suppose we have the following "grid world":
\begin{center}
\begin{picture}(100,90)
\put(0,8){\large{c}}
\put(0,33){\large{b}}
\put(0,58){\large{a}}
\put(20,77){\large{1}}
\put(45,77){\large{2}}
\put(70,77){\large{3}}
\put(95,77){\large{4}}
\multiput(10,0)(0,25){4}{\line(1,0){100}}
\multiput(10,0)(25,0){5}{\line(0,1){75}}
\put(35,25){\rule{25pt}{25pt}}
\color{red}
\put(18,6){\Large\textbf{S}}
\put(87,33){\textbf{-100}}
\put(90,58){\textbf{100}}
\end{picture}
\end{center}
The agent starts at square \color{red}\textbf{S}\color{black}. The two states with rewards attached are called \textbf{absorbing states}. To make this an MDP, assume that actions are stochastic. Suppose that if the agent attempts to move in a given direction, it has an 80\% chance of succeeding, but a 10\% chance for each of the perpendicular directions. For example, a "North" action results in an 80\% chance of moving North, a 10\% chance of moving West, and a 10\% chance of moving East. Attempting to move to an illegal position will result in the agent remaining where it is.

Clearly, conventional planning would be insufficient in this example, because we cannot be sure of the outcome of our actions.

\begin{defin}[Policy]
A \emph{\textbf{policy}} is a function $\pi(S)\rightarrow A$ that provides an action for every possible state.
\end{defin}

A policy for our example problem might look like the following:
\begin{center}
\begin{picture}(100,90)
\put(0,8){\large{c}}
\put(0,33){\large{b}}
\put(0,58){\large{a}}
\put(20,77){\large{1}}
\put(45,77){\large{2}}
\put(70,77){\large{3}}
\put(95,77){\large{4}}
\multiput(10,0)(0,25){4}{\line(1,0){100}}
\multiput(10,0)(25,0){5}{\line(0,1){75}}
\put(35,25){\rule{25pt}{25pt}}
\color{red}
\put(18,6){\Large\textbf{S}}
\put(87,33){\textbf{-100}}
\put(90,58){\textbf{100}}
\thicklines
\put(23,20){\vector(0,1){15}}
\put(23,45){\vector(0,1){15}}
\put(30,63){\vector(1,0){15}}
\put(55,13){\vector(1,0){15}}
\put(55,63){\vector(1,0){15}}
\put(73,20){\vector(0,1){15}}
\put(73,45){\vector(0,1){15}}
\put(90,13){\vector(-1,0){15}}
\put(80,63){\vector(1,0){15}}
\end{picture}
\end{center}

\paragraph{Conventional versus Markov planning in stochastic environments.} If we were to attempt to plan by building a tree of the possible outcomes for this example, we would have the following:

\Tree [.c1 [.N b1 c1 c2 ] [.S c1 c2 ] [.W c1 b1 ] [.E c2 c1 b1 ] ]

\noindent In general, each action will have up to 3 possible outcomes. Thus, every two levels that we descend could create up to 12 new nodes.

The major problems that are overcome with a policy are:
\begin{itemize_packed}
\item Large branching factor.
\item Tree too deep: we could potentially get stuck in an infinite loop.
\item Many states could be visited more than once.
\end{itemize_packed}

Now consider the case where we use a policy. Observe that it is possible to create a policy that will never end up in the -100 state. For example, if the agent is in position c4, it could choose to continually perform action "South", with a 90\% chance of not moving and a 10\% chance of moving West.

The inconvenience here is that it may take a long time for the agent to arrive at its goal. We can account for this by modifying the reward function so that each move has a cost involved. For example, we might say
\begin{center}
$R(s) =
\begin{cases}
+100 & \text{if } s = a4 \\
-100 & \text{if } s = b4 \\
-3 & \text{all other states}
\end{cases}$
\end{center}
thus providing an incentive to make the path short. We may therefore formally state the goal of an MDP: to maximize the expected value of all future rewards.
\begin{center}
$\displaystyle E\left[\sum_{t=0}^{\infty} \gamma^t R_t \right] \rightarrow$ max
\end{center}
In this equation, $R_t$ is the reward at time $t$, and $E$ is the expected value function. $\gamma$ is called the \textbf{discount factor}. When given a value in $(0,1)$, it is an alternative to the negative reward of -3 used above, used to provide an incentive to find a reward sooner. The advantage of using $\gamma$ here is that we can bound the value of the expected value function:
\begin{center}
$\displaystyle E[\ldots] \leq \frac{1}{1-\gamma} |R_{\text{max}}|$
\end{center}

Using this, we may define a \textbf{value function} for each state, given our policy $\pi$.
\begin{center}
$\displaystyle V^\pi(s) = E_\pi \left[ \sum_t \gamma^t R_t | s_0 = s \right]$
\end{center}
Planning using MDPs involves calculating the value function for each state.

\paragraph{Value iteration.} The value function can be calculated iteratively. We initially assign a value of 0 to all non-goal states. We then start with state a3:
\begin{center}
$V(a3,E) = 0.8*100 + 0.1*0 + 0.1*0 - 3 = 77$
\end{center}
We can then propagate this value for neighboring states:
\begin{center}
\begin{tabular}{r@{ } @{}l@{} @{ }l}
$V(a2,E) $ & $= 0.8*77 + 0.1*0 + 0.1*0 - 3 $ & $= 58.6$ \\
$V(b3,E) $ & $= 0.8*77 + 0.1*(-100) + 0.1*0 - 3 $ & $= 48.6$
\end{tabular}
\end{center}
We continue this process until an initial value is assigned to all states. We can then repeat the process, using our new values, to get a better estimate.
\begin{center}
$V(a3,E) = 0.8*100 + 0.1*77 + 0.1*48.6 - 3 = 89.56$
\end{center}
If we continue to repeat this process, the values will converge to the true value for each state. This can be summarized with the following formula:
\begin{center}
$\displaystyle V(s) \leftarrow \left[ \max_a \gamma \sum_{s'}P(s'|s,a)V(s')\right] + R(s)$
\end{center}
where $a$ is the action that maximizes the sum, the sum is over all possible successor states $s'$ of $a$, and $V(s')$ is the current value of the successor state $s'$. This algorithm is called \textbf{back-up}. There is a theorem which states that this equation will converge.

Back-up clearly helps us to find the optimal policy: the action to take for any square is the one that maximizes the expression for the value function.
\begin{center}
$\displaystyle \pi(s) = \operatorname*{arg\,max}_a \sum_{s'}P(s'|s,a)V(s')$
\end{center}

\paragraph{Summary.} With Markov Decision Processes, we have
\begin{itemize_packed}
\item a \underline{fully observable} environment: we have states $s_1,\ldots,s_N$ and actions $a_1,\ldots,a_k$
\item a \underline{stochastic} environment: we only know $P(s'|a,s)$
\item a \underline{reward function} for each state: $R(s)$
\item the objective of \underline{maximizing the future reward}: $\max E(\sum_t \gamma^t R_t)$
\item the key to solving an MDP is \underline{value iteration}, which
\item converges to the \underline{optimum} policy.
\end{itemize_packed}

\section{Partially Observable Markov Decision Process (POMDP)}

%===============================================================================

\part{Reinforcement Learning}

This unit builds on the previous one by asking the question: how can the agent find an optimal policy, if it initially knows nothing about the rewards?

\paragraph{Review.} We have the following types of learning:
\begin{itemize_packed}
\item supervised, where we are given data points $(x_1, y_1)$, $(x_2,y_2)$, \ldots, and we wish to find an optimal function to calculate $y = f(x)$
\item unsupervised, where we have data points $x_1,x_2,\ldots$, and we attempt to find patterns in the data, or probabilities $P(X=x)$
\item reinforcement, where we have a series of state-action transitions $s,a,s,a,s,\ldots$, where each state has a reward associated, and we attempt to determine an optimal policy $\pi(s)$.
\end{itemize_packed}

Reinforcement agents differ in that we do not necessarily know the reward function, or even the probability of the outcome of an action. There are several types of agents that we can use, based on the situation.
\begin{center}
\begin{tabular}{c c c c}
agent & know & learn & use \\
\hline
utility-based agent & P & R$\rightarrow$U & U \\
Q-learning agent & & $Q(s,a)$ & $Q$ \\
reflex agent & & $\pi(s)$ & $\pi$
\end{tabular}
\end{center}
In addition, there are two ways we can vary these agents.

\begin{defin}
A \emph{\textbf{passive}} reinforcement learning agent has a fixed policy, and learns about R and P while executing that policy.
\end{defin}

\begin{defin}
An \textbf{active} reinforcement learning agent modifies its policy during execution.
\end{defin}

For example, suppose that your agent are a passenger on a ship navigating uncharted waters. A passive agent is unable to change the captain's policy; however, it can still observe the actions (directions) that the ship takes, and learn about the environment. An active agent would be allowed to take control of the ship, and act on the knowledge it already has, perhaps enabling it to explore and continue to learn.

\paragraph{Passive Temporal Difference Learning} This algorithm propagates the utility of each state backwards on each iteration. It thus requires many iterations in order to propagate values back from the end to the start state. The values of the utility function converge to the true utility.

\begin{algorithm}
\caption{Passive Temporal Difference Learning}
\begin{algorithmic}[1]
\IF{$s'$ is new}
	\STATE{$U[s']\leftarrow r'$}
\ENDIF
\IF{$s$ is not null}
	\STATE{increment $N_s[s]$}
	\STATE{$U[s]\leftarrow U[s] + \alpha(N_s[s])(r + \gamma U[s'] - U[s])$}
\ENDIF
\end{algorithmic}
\end{algorithm}

This algorithm has several potential weaknesses, notably:
\begin{itemize_packed}
\item it may take a long time to converge
\item what it can learn is limited by the policy that it is given
\item due to the policy, there may be states to which it cannot assign a utility
\item even for states with a utility assigned, this may be a poor estimate.
\end{itemize_packed}

Some of these shortcomings may be addressed by \textbf{Active Greedy Temporal Difference Learning}. This algorithm re-computes the MDP ideal policy at the end of each iteration, taking into account the current utility estimates.

%===============================================================================

\part{Hidden Markov Models (HMMs)}

Consider the following Bayes Network:
\begin{center}
\begin{picture}(150,60)
\thicklines
\put(3,40){$S_1$}
\put(8,42){\circle{17}}
\put(16,42){\vector(1,0){16}}
\put(8,34){\vector(0,-1){16}}

\put(35,40){$S_2$}
\put(40,42){\circle{17}}
\put(48,42){\vector(1,0){16}}
\put(40,34){\vector(0,-1){16}}

\put(65,41){\ldots}

\put(80,40){$S_N$}
\put(85,42){\circle{17}}
\put(85,34){\vector(0,-1){16}}

\put(3,7){$Z_1$}
\put(8,9){\circle{17}}

\put(35,7){$Z_2$}
\put(40,9){\circle{17}}

\put(80,7){$Z_N$}
\put(85,9){\circle{17}}

\put(100,40){Markov Chain}
\put(100,7){Measurements}

\end{picture}
\end{center}
The states of the Markov Chain are unknown, and we must infer information about them from the measurements. The distinguishing feature of a Markov Chain is that the past, the future, and the present measurement, are all conditionally independent given the present state.

\section{Markov Chains}

Suppose we have the following Bayes Network describing the transitions from rainy (R) and sunny (S) days.
\begin{center}
\begin{picture}(85,40)
\put(0,0){\usebox{\rainySunnyBox}}
\end{picture}
\end{center}
We define $P(R_t)$ and $P(S_t)$ to be the probabilities that it is rainy or sunny at time $t$. If we are given that $P(R_0) = 1$, we can calculate the probabilities that it will be rainy or sunny at any given time in the future.
\begin{center}
\begin{tabular}{r@{ } @{}c@{} @{ }l}
$P(R_1)$ & $=$ & $P(R_1|R_0)P(R_0)$ \\
& $=$ & $0.6$ \\
$P(S_1)$ & $=$ & $1 - P(R_1)$ \\
& $=$ & $0.4$ \\
$P(R_2)$ & $=$ & $P(R_2|R_1)P(R_1) + P(R_2|S_1)P(S_1)$ \\
& $=$ & $0.6 * 0.6 + 0.2 * 0.4$ \\
& $=$ & $0.44$
\end{tabular}
\end{center}

\paragraph{Stationary distribution.} Another question that we might ask is, what is the probability that we are in a given state at any given time? For this, we can calculate the \textbf{stationary distribution} by solving the equation
\begin{center}
\begin{tabular}{r@{} @{ }c@{ } @{}l}
$P(R_{t-1})$ & $=$ & $P(R_t)$ \\
& $=$ & $P(R_t|R_{t-1})P(R_{t-1}) + P(R_t|S_{t-1})P(S_{t-1})$ \\
& $=$ & $P(R_t|R_{t-1})P(R_{t-1}) + P(R_t|S_{t-1})(1 - P(R_{t-1}))$
\end{tabular}
\end{center}
from which we solve
\begin{center}
$\displaystyle P(R_{t-1}) = \frac{P(R_t|S_{t-1})}{1 - P(R_t|R_{t-1}) + P(R_t|S_{t-1})}$
\end{center}

\paragraph{Learning from data.} In the absence of explicit probabilities, we can observe the system and attempt to learn the probabilities from a given data set. For example, suppose we observe the weather sequence
\begin{center}
SSSSSRSSSRR.
\end{center}
Using maximum likelihood, we calculate that
\begin{center}
\begin{tabular}{r@{} @{ }c@{ } @{}l}
$P(R_0)$ & $=$ & $0$ \\
$P(S_{t+1}|S_t)$ & $=$ & $0.75$ \\
$P(R_{t+1}|S_t)$ & $=$ & $1 - P(S_{t+1}|S_t)$ \\
& $=$ & $0.25$ \\
$P(S_{t+1}|R_t)$ & $=$ & $0.5$ \\
$P(R_{t+1}|R_t)$ & $=$ & $1 - P(S_{t+1}|R_t)$ \\
& $=$ & $0.5$ \\
\end{tabular}
\end{center}
However, it is often preferable to use Laplacian Smoothing to estimate the probabilities in this case.

\paragraph{Hidden Markov Models.} The \textbf{hidden} part of the model comes from the following: suppose that we do not actually know the values of $R_t$ and $S_t$, but instead we only have observations that tell us something about them. For example, suppose that we can observe only whether the professor is happy or grumpy, and that we know with what probabilities the weather can affect his mood. We might have the following diagram:
\begin{center}
\begin{picture}(85,70)
\put(0,30){\usebox{\rainySunnyBox}}
\thicklines
\color{red}
\put(20,45){\vector(-1,-4){8}}
\put(60,45){\vector(-1,-4){8}}
\put(26,45){\vector(1,-4){8}}
\put(66,45){\vector(1,-4){8}}

\put(7,2){H}
\put(32,2){G}
\put(47,2){H}
\put(72,2){G}

\put(0,25){0.4}
\put(31,30){0.6}
\put(40,22){0.3}
\put(73,25){0.1}
\end{picture}
\end{center}
Now, suppose that we are given that $P(R_0) = P(S_0) = 0.5$. We may wish to determine the probability of the weather for the following day, given only an observation about the professor's mood: $P(R_1|H_1)$. To calculate this, we use Bayes' Rule:
\begin{center}
$\displaystyle P(R_1|H_1) = \frac{P(H_1|R_1)P(R_1)}{P(H_1)}$
\end{center}
We see from the diagram that $P(H_1|R_1) = 0.4$, and we already learned how to calculate $P(R_1) = 0.4$ and $P(H_1) = 0.16 + 0.54 = 0.7$. This expression therefore evaluates to about 0.229.

\paragraph{Summary.} We have learned how to use HMMs to do two things:
\begin{itemize_packed}
\item \textbf{State Estimation} means computing the probability of internal (hidden) states, given measurements.
\item \textbf{Prediction} is used to calculate not only the next state, but also the next measurement.
\end{itemize_packed}

\section{Particle Filters}

Particle filters are a method of guessing the possible state of an agent in a stochastic environment, where the agent's sensors may not be precise. Initially, the "particles" are spread evenly throughout the state space. As the agent (a robot, for example) moves through the environment, it weights the particles based on the probability of the agent being at that particle, given the previous measurements. At each iteration, the algorithm creates a new set of particles; however, instead of distributing them evenly, they are selected from the previous set of weighted particles, using the weight as the probability that they will be selected.

Particle filters have the following pros and cons:
\begin{itemize_packed}
\item They are easy to implement.
\item They don't work well in high-dimensional spaces, due to the number of particles required.
\item They don't work well with discrete environments. They are more adapted to environments with some "noise" added.
\end{itemize_packed}

The following algorithm is repeated for each measurement; the basic sequence is
\begin{itemize_packed}
\item Look at the measurements
\item Compute the weights
\item Sample
\item Predict
\end{itemize_packed}

\begin{algorithm}
\caption{Particle Filter Algorithm}
\begin{algorithmic}[1]
\REQUIRE A set $S$ of particles, with their associated importance weights, a control vetor $u$ and a measurement vector $Z$
\ENSURE A new set $S'$ of particles, with their weights adjusted according to the measurement $Z$

\STATE{$S' = \emptyset$ and $\eta = 0$}

\FOR{$i = 1\ldots |S|$}
	\STATE{sample $j ~ \{w\}$ with replacement}
	\STATE{$x' ~ P(x' | u, s_j)$}
	\STATE{$w' = P(Z|x')$}
	\STATE{$\eta = \eta + w'$}
	\STATE{$S' = S' \cup \{<x', w'>\}$}
\ENDFOR

\FOR{$i = 1\ldots |S'|$}
	\STATE{$w_i = w_i / \eta$}
\ENDFOR
\end{algorithmic}
\end{algorithm}

%===============================================================================

\part{Games}

A game can be described using the following parameters:
\begin{itemize_packed}
\item A set of states $S$ with an initial state $s_0$
\item A set of players $P$
\item A set of possible actions for each player at a given state $Actions(s,p)$
\item A transition function $Result(s,a)\rightarrow s'$
\item An end-game test $Terminal(s)\rightarrow \{true, false\}$
\item A utility function $U(s,p)\rightarrow \mathbb{R}$ indicating the value of a given state for a given player. In simple games, this might simply be 0 or 1.
\end{itemize_packed}

\paragraph{Example.} Consider the games of checkers and chess. These games are
\begin{itemize_packed}
\item \textbf{deterministic}
\item \textbf{two-player}
\item \textbf{zero-sum}, i.e. the sum of the utilities to the two players is 0. If one player gets +1 for winning, the other player gets -1 for losing.
\end{itemize_packed}
To solve this game, we can start by building a search tree of all possible states and actions. All even nodes (i.e. at depth 0, 2, 4, ...) represent a decision by the first player, and all odd nodes represent a decision by the second.
In building the tree, we eventually reach the terminal states of the game, with values +1 if player 1 wins, and -1 if player 2 wins. We can then backtrack up the tree, assigning values to preceding nodes by assuming that, when given a choice, each player will act rationally. By filling the tree in this way, we eventually determine a winning move for each player at each state.
For example, let player 1 be $\triangle$ and player 2 be $\nabla$. We start with the following tree.
\begin{center}
\Tree [.$\triangle$ [.$\nabla$ $\triangle$ $\triangle$ [.$\vdots$ [.$\triangle$ {+1} {-1} ] ] ] [.$\nabla$ $\triangle$ $\triangle$ ] [.$\nabla$ $\triangle$ $\triangle$ ] ]
\end{center}
Since player 1 wishes to maximize the reward, given the choice between +1 and -1, it will choose +1. Thus, we can assign the value +1 to the node directly above the terminal states.
\begin{center}
\begin{tabular}{r c l}
\Tree [.$\triangle$ {+1} {-1} ] & $\longrightarrow$ & \Tree [.{+1} {+1} {-1} ]
\end{tabular}
\end{center}
We then backtrack up the tree, assigning values to each node.

The basic algorithm just described is the following.
\begin{algorithm}
\caption{value}
\begin{algorithmic}[1]
\REQUIRE A state s
\ENSURE The value of the state s
\IF{$Terminal(s)$}
	\RETURN $U(s)$
\ENDIF
\IF{s is player 1}
	\RETURN $maxValue(s)$
\ENDIF
\IF{s is player 2}
	\RETURN $minValue(s)$
\ENDIF
\end{algorithmic}
\end{algorithm}

\noindent The $maxValue$ and $minValue$ functions return the maximum and minimum value of all successor states of a node.

The problem with this approach is that it can be expensive in terms of space and time. If the branching factor (the average number of branches from a node) is $b$, and the average depth of the tree is $m$, then the run-time of the tree search algorithm will be $O(b^m)$. Since the $maxValue$ function is depth-first, only $O(bm)$ space would be required.

Clearly, this is impossibly impractical for games like chess, where $b$ is in the dozens and $m$ can be very long. One technique is to attempt to reduce the size of the tree, by either reducing $b$, $m$ or using GraphSearch.

\paragraph{Reducing $b$.} Suppose we have the following tree.
\begin{center}
\Tree [.$\triangle$ [.$\nabla$ 3 12 8 ] [.$\nabla$ 2 3 9 ] [.$\nabla$ 14 1 8 ] ]
\end{center}
We know that $\triangle$ wishes to maximize the value, and $\nabla$ wishes to minimize. We start by assigning the value 3 to the first $\nabla$ node. Observe that, for the second $\nabla$ node, the first child node's value is 2. We therefore know that the value for this $\nabla$ will be $\leq$ 2. Since $\triangle$ wishes to maximize the value, we know that it will not choose this path, and it is no longer necessary to continue calculating the value for the other children. Likewise, on the third $\nabla$ node, once we find the 1, it is no longer necessary to calculate the 8. We can thus prune the tree as follows.
\begin{center}
\Tree [.$\triangle$ [.3 3 12 8 ] [.{$\leq 2$} 2 ] [.{$\leq 1$} 14 1 ] ]
\end{center}

\paragraph{Reducing $m$.} One way to reduce the depth of the tree is simply to stop searching at a given depth, treating all nodes at that depth as terminal nodes. The question then arises of how to assign a value to these pseudo-terminal nodes. An \textbf{evaluation function} $ev(s)$ attempts to estimate the value of the state $s$. We assign the value of $ev(s)$ to each new child node.
\newline
\newline
We can use these two techniques to revise the $value$ function.
\begin{algorithm}
\caption{value (optimized)}
\begin{algorithmic}[1]
\REQUIRE A state s, a maximum depth, $\alpha$ = the highest $maxValue$, $\beta$ = the lowest $minValue$
\ENSURE The value of the state s
\IF{cutoff$(s,depth)$}
	\RETURN $ev(s)$
\ENDIF
\IF{$Terminal(s)$}
	\RETURN $U(s)$
\ENDIF
\IF{s is player 1}
	\RETURN $maxValue(s, depth, \alpha, \beta)$
\ENDIF
\IF{s is player 2}
	\RETURN $minValue(s, depth, \alpha, \beta)$
\ENDIF
\end{algorithmic}
\end{algorithm}

\noindent This algorithm would be initially called with $value(S_0, 0, -\infty, +\infty)$. We revise the $maxValue$ function as follows.
\begin{algorithm}
\caption{maxValue (optimized)}
\begin{algorithmic}[1]
\REQUIRE A state s, a maximum depth, $\alpha$ = the highest $maxValue$, $\beta$ = the lowest $minValue$
\ENSURE The value of the state s
\STATE v = $-\infty$
\FOR{$a$, $s'$ in $successors(s)$}
	\STATE $v = \max(v, value(s', depth+1, \alpha, \beta))$
	\IF{$v \geq \beta$}
		\RETURN $v$
	\ENDIF
	\STATE $\alpha = \max(\alpha, v)$
\ENDFOR
\RETURN $v$
\end{algorithmic}
\end{algorithm}

\paragraph{Summary.} We looked at the following optimizations.
\begin{itemize_packed}
\item \textbf{$\alpha-\beta$ pruning}: can potentially reduce the run-time from $O(b^m)$ to $O(b^{m/2})$.
\item \textbf{Evaluation functions}
\item \textbf{Converting to a graph}.
\end{itemize_packed}

\paragraph{Chance.} What can we do if the game is stochastic? In this case, when we arrive at a turn where the outcome of a move is not clear, we consider the value of that node to be the \textbf{expected value} of all possible results.

%===============================================================================

\part{Game Theory}

\begin{defin}
\emph{\textbf{Game Theory}} is the study of finding an optimal policy, when that policy can depend on an opponent's policy (and vice-versa).
\end{defin}

\paragraph{The Prisoner's Dilemma.} Suppose that two people, Alice and Bob, have been arrested for collaborating on a crime. The police question each individual separately. If each remains silent, the police will only have some evidence, and they will each get a light sentence. If one of them testifies against the other, then that one will be released, and the other will get a heavy sentence. If they both agree to testify, then they will both get moderate sentence.

We can model this situation using the following grid.
\begin{center}
\begin{tabular}{r|c|c|}
\multicolumn{1}{r}{} & \multicolumn{1}{c}{A:testify} & \multicolumn{1}{c}{A:refuse} \\
\cline{2-3}
B:testify & A = -5, B = -5 & A = -10, B = 0 \\
\cline{2-3}
B:refuse & A = 0, B = -10 & A = -1, B = -1 \\
\cline{2-3}
\end{tabular}
\end{center}
What strategy should Alice and Bob follow?

\begin{defin}
A \emph{\textbf{Dominant Strategy}} is one for which a player does better than any other strategy, no matter what the other player does.
\end{defin}

\begin{defin}
A \emph{\textbf{Pareto Optimal}} outcome is an outcome such that there is no other outcome that all players would prefer.
\end{defin}

\begin{defin}
An \emph{\textbf{equilibrium}} is an outcome such that no player can benefit from a different strategy, assuming that the other players stay the same.
\end{defin}

For Alice and Bob, the Dominant Strategy for each would be to testify; however, the Pareto optimal outcome only occurs when both refuse. The equilibrium also occurs when both testify.

Consider another example, where Acme makes video game systems, and Best makes video games, and each must decide what format to use for the games (DVD or Blu-Ray).
\begin{center}
\begin{tabular}{r|c|c|}
\multicolumn{1}{r}{} & \multicolumn{1}{c}{A:blu} & \multicolumn{1}{c}{A:dvd} \\
\cline{2-3}
B:blu & A = 9, B = 9 & A = -4, B = -1 \\
\cline{2-3}
B:dvd & A = -3, B = -1 & A = 5, B = 5 \\
\cline{2-3}
\end{tabular}
\end{center}
There is no dominant strategy here: the best choice for each player depends on what the other player will do. There are two equilibrium points that occur when both A and B choose the same format. The Pareto optimal outcome is when both choose Blu-Ray.

\paragraph{Two-finger morra.} Consider another game, where we have two players, Even and Odd. On each turn, each player shows one or two fingers. If the sum of all fingers is even, then Even wins that number of dollars, and if the sum is odd, then Odd wins that many. We have the following matrix (this is a zero-sum game, so we only note the outcome for Even).
\begin{center}
\begin{tabular}{r|c|c|}
\multicolumn{1}{r}{} & \multicolumn{1}{c}{O:one} & \multicolumn{1}{c}{O:two} \\
\cline{2-3}
E:one & E = 2 & E = -3 \\
\cline{2-3}
E:two & E = -3 & E = 4 \\
\cline{2-3}
\end{tabular}
\end{center}
Clearly, there is no dominant strategy for this game.

\begin{defin}
A single strategy of always playing the same move is called a \emph{\textbf{pure}} strategy, whereas a \emph{\textbf{mixed}} strategy is one where we have a probability distribution over all moves.
\end{defin}
A mixed strategy is used when there is no dominant (pure) strategy available.
\\

It may be easier to consider this game if represented using trees. The left branch represents choosing 1, and the right branch represents choosing 2.
\begin{center}
\Tree [.E:-3 [.O:-3 2 -3 ] [.O:-3 -3 4 ] ]
\Tree [.O:2 [.E:2 2 -3 ] [.E:4 -3 4 ] ]
\end{center}
In each situation, the starting player is severely handicapped, because he must reveal his strategy. We might instead consider a mixed strategy, in which the starting player announces that he will choose 1 with probability $p$ (and thus, he will choose 2 with probability $1-p$).
\begin{center}
\Tree [.{E\\ $p$:one, $(1-p)$:two} [.O {$2p - 3(1-p)$} {$-3p + 4(1-p)$} ] ]
\Tree [.{O\\ $q$:one, $(1-q)$:two} [.E {$2q - 3(1-q)$} {$-3q + 4(1-q)$} ] ]
\end{center}
Each player would then wish to choose the value of $p$ or $q$ that causes the leaves to be equal. Solving these equations yields that $p=q=\frac{7}{12}$. We thus can calculate the that utility of this strategy to E is $U_E = -\frac{1}{12}$.

\paragraph{Strategies.} In practice, such approaches are often impractical. For example, in poker, the state space is around $10^{18}$ possibilities. We can try to reduce the state space in various ways. For example, we might ignore the suit of the cards; we might lump cards together (for example, if I'm holding tens, I can consider all the other cards as greater or less than 10); or I could simply only consider a sub-set of all possible cards.

In general, Game Theory is good at handling
\begin{itemize_packed}
\item uncertainty
\item partial observability
\item multiple agents
\item stochastic environments
\item dynamic environments.
\end{itemize_packed}
However, it is less powerful with
\begin{itemize_packed}
\item unknown actions
\item continuous actions
\item irrational opponents
\item unknown utilities.
\end{itemize_packed}

%===============================================================================

\part{Advanced Planning}

We will discuss:
\begin{itemize_packed}
\item \textbf{time}: actions that persist over a length of time
\item \textbf{resources} necessary to complete a task
\item \textbf{active perception}
\item \textbf{hierarchical plans}, i.e. steps with sub-steps
\end{itemize_packed}

\paragraph{Scheduling.} We may have a scheduling network of tasks that we must complete. The start state is $S$ and the final state is $F$. Each task takes a certain amount of time to complete. We define $ES$ to be the earliest start time and $LS$ the latest start time for which it is possible to finish the network in the shortest possible amount of time. We can calculate them recursively:
\begin{center}
\begin{tabular}{r@{} @{ }c@{ } @{}l}
$ES(s)$ & $=$ & $0$ \\
$ES(B)$ & $=$ & $max_{A\rightarrow B} ES(A) + Duration(A)$ \\
$LS(F)$ & $=$ & $ES(f)$ \\
$LS(A)$ & $=$ & $min_{B\leftarrow A} LS(B) - Duration(A)$
\end{tabular}
\end{center}

\paragraph{Example.}
\begin{center}
\begin{picture}(200,80)
% Dimensions 20,36
\put(20,25){\schedulingNode{S}{0}{0}}
\put(39,35){\vector(2,-1){25}}
\put(39,51){\vector(2,1){25}}

\put(60,0){\schedulingNode{60}{0}{0}}
\put(79,18){\vector(1,0){25}}
\put(100,0){\schedulingNode{15}{60}{60}}
\put(119,18){\vector(1,0){25}}
\put(140,0){\schedulingNode{10}{75}{75}}
\put(159,18){\vector(2,1){25}}

\put(60,50){\schedulingNode{30}{0}{15}}
\put(79,68){\vector(1,0){25}}
\put(100,50){\schedulingNode{30}{30}{45}}
\put(119,68){\vector(1,0){25}}
\put(140,50){\schedulingNode{10}{60}{75}}
\put(159,68){\vector(2,-1){25}}

\put(180,25){\schedulingNode{F}{85}{85}}

\color{red}
\put(0,51){Dur.}
\put(0,40){$ES$}
\put(0,29){$LS$}
\end{picture}
\end{center}

\paragraph{Resources.}

\paragraph{Hierarchical Planning.} In practice, it is often impossible to model and plan for all possible actions. Instead, we can use a \textbf{Hierarchical Transition Network} to model higher-order, abstract plans, that are composed of several smaller sub-steps. This idea is called \textbf{refinement planning}. Each higher-order plan is composed of multiple \textit{refinements}, which describe how to complete the plan. The overall plan can be achieved provided that each higher-order plan has a refinement that can be achieved.

\paragraph{Reachable States.} We can also solve a problem using refinement of belief states. From the starting state, we can enumerate all the possible successor states, and then all successors of the successors, until we end up with a successor state that contains a goal state. We then start at the goal state and backtrack until we reach the initial state.

%===============================================================================

\part{Computer Vision I}

\paragraph{Cameras.} A pinhole camera can be defined by its focal length, image depth, and the height of the object being photographed. These values satisfy the equation
\begin{center}
$\displaystyle x = X * \frac{f}{Z}$
\end{center}
where $X$ is the height of the object, $x$ is the height of the image of the object, $f$ is the focal length, and $Z$ is the distance from the object to the camera. This is known as the \textbf{perspective law}, and can be used to find the distance to an object, given that object's actual height.

Computer vision can be used to
\begin{itemize_packed}
\item classify objects;
\item perform 3D reconstruction;
\item perform motion analysis.
\end{itemize_packed}

\paragraph{Object recognition.} One problem is to attempt to identify objects that the computer sees. A key concept is \textbf{invariance}, which refers to the fact that the image will have natural variations that don't affect the object itself, and so the software must be invariant with respect to those natural variations. These variations may include
\begin{itemize_packed}
\item scale
\item illumination
\item rotation
\item deformation
\item occlusion
\item view point.
\end{itemize_packed}
Ideally, we would want to write software that is invariant in spite of these variances in the image of the object.

Grayscale images are often used instead of color images, because they are less variant with respect to lighting changes. A grayscale image can be represented by a matrix of 8-bit intensity values.

We often start by attempting to extract \textbf{features} from the image, such as lines or corners. For example, we might apply a \textbf{mask} (or \textbf{kernel}) wherein we subtract the value of the pixel to the right of our current pixel.
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
255 & 212 & 7 & 1 & 3 \\
\hline
211 & 237 & 3 & 9 & 0 \\
\hline
218 & 240 & 8 & 12 & 2 \\
\hline
241 & 241 & 5 & 4 & 0 \\
\hline
\end{tabular}
$\otimes$
\begin{tabular}{|c|c|}
\multicolumn{2}{c}{\textbf{mask}} \\
\hline
+1 & -1 \\
\hline
\end{tabular}
$=$
\begin{tabular}{|c|c|c|c|}
\hline
43 & 205 & 6 & -2 \\
\hline
-26 & 234 & -6 & 9 \\
\hline
-22 & 232 & -4 & 10 \\
\hline
0 & 236 & 1 & 4 \\
\hline
\end{tabular}
\end{center}
In this example, the second column (after applying the mask) stands out quite clearly from the others. There is obviously a vertical line here.

This type of operation is called a \textbf{Linear Filter}. Mathematically, we can express a linear filter as a function $g$ from an image (matrix) $I$ to the resulting image $I'$ as
\begin{center}
$\displaystyle I'(x,y) = \sum_{u,v} I(x-u, y-v) \cdot g(u,v)$.
\end{center}

Similarly to the previous example, we could use a vertical filter to find horizontal edges in the image. If we define
\begin{center}
$I_x = I \otimes$
\begin{tabular}{|c|c|}
\hline
-1 & +1 \\
\hline
\end{tabular}

$I_y = I \otimes$
\begin{tabular}{|@{}c@{}|}
\hline
+1 \\
\hline
-1 \\
\hline
\end{tabular}
\end{center}
(in other words, the gradient of the image is $(I_x, I_y)$) then we can define the \textbf{gradient image} $E$ to be
\begin{center}
$\displaystyle E = \sqrt{(I_x)^2 + (I_y)^2}$.
\end{center}
The gradient image captures all lines where there is a strong transition between dark and light.

This technique can be improved even further using a \textbf{Canny edge detector}.

In general, there exist several different types of kernels that can be used. One type, called a \textbf{Gaussian kernel}, is a matrix with high values in the center, which drop off exponentially toward the edges. Using such a kernel will result in a blurred image. This can be useful for several reasons, including:
\begin{itemize_packed}
\item \textbf{Down-sampling}. Using Gaussian kernel before shrinking an image is more effective than selecting individual pixels from the original.
\item \textbf{Noise reduction}. Blurring the image can smooth away noise.
\end{itemize_packed}

The convolution operation is associative: if we perform the operation
\begin{center}
$I \otimes f \otimes g$,
\end{center}
where $f$ is a Gaussian kernel and $g$ is a gradient kernel, we can associate $f$ and $g$, resulting in a single kernel $(f\otimes g)$ to be applied to $I$.

\paragraph{Corner detection.} It may be more useful to detect corners than to detect edges, since it can be difficult to identify one's position on an edge. If we find a neighborhood of points where
\begin{center}
$\sum (I_x)^2 \rightarrow$ large
$\sum (I_y)^2 \rightarrow$ large
\end{center}
then there is probably a corner here, composed of horizontal and vertical edges. However, if the corner is rotated, these values won't stand out as much. \textbf{Harris Corner Detection} instead uses the matrix
\begin{center}
$\begin{pmatrix}
\sum (I_x)^2 & \sum I_xI_y \\
\sum I_xI_y & \sum (I_y)^2
\end{pmatrix}$
\end{center}
and then calculates its eigenvalues. If the eigenvalues are large, then there is a corner here.

\paragraph{Modern feature detection.} Today's algorithms, similar to Harris corner detection, are localizable, but also have unique signatures, gathering data that is invariant under scaling or rotation. Two main algorithms are
\begin{itemize_packed}
\item \textbf{HOG} (histogram of oriented gradients)
\item \textbf{SIFT} (scale invariant feature transform).
\end{itemize_packed}

%===============================================================================

\part{Computer Vision II (3d vision)}

A key problem when using a camera is to attempt to determine the depth of an image: the distance from the object to the camera. One way to get more information to capture the depth of an object is to use \textbf{stereo vision}, i.e. two cameras. We have the following situation:
\begin{center}
\begin{picture}(200,100)
\thicklines
\put(10,0){\line(0,1){42}}
\put(20,0){\line(0,1){20}}
\put(20,21){\line(0,1){20}}

\put(10,50){\line(0,1){42}}
\put(20,50){\line(0,1){20}}
\put(20,71){\line(0,1){20}}

\put(5,20){\line(0,1){50}}
\put(7,20){\line(-1,0){5}}
\put(7,70){\line(-1,0){5}}
\put(-9,42){$B$}

\put(120,45){\circle*{3}}
\put(118,48){$P$}

\color{red}
\put(20,20){\line(4,1){120}}
\put(20,70){\line(4,-1){120}}
\put(118,45){\vector(-1,0){99}}
\put(50,47){$Z$}

\color{blue}
\put(20,20){\line(-4,-1){10}}
\put(20,20){\line(-1,0){10}}
\put(20,70){\line(-4,1){10}}
\put(20,70){\line(-1,0){10}}

\put(10,45){\vector(1,0){11}}
\put(12,49){$f$}

\put(5,20){\line(0,-1){3}}
\put(7,17){\line(-1,0){5}}
\put(-9,17){$x_2$}
\put(5,70){\line(0,1){3}}
\put(7,73){\line(-1,0){5}}
\put(-9,70){$x_1$}

\end{picture}
\end{center}
from which we deduce the following equation.
\begin{center}
$\displaystyle \frac{x_2 - x_1}{f} = \frac{B}{Z} \;\;\Rightarrow\;\; Z = \frac{fB}{x_2 - x_1}$
\end{center}

\paragraph{Correspondence, aka Data Association.} Suppose we find an interesting point on one camera, and we wish to find that point in the other camera. If we do not know the depth of the point, then the most we know is that it occurs somewhere on the ray that goes from the point's image on the camera's sensor, to the actual point. The projection of this ray onto the second camera will be a line; thus, instead of searching everywhere on the second camera's image for our point, we can simply search along the projection of the ray.
\begin{center}
\begin{picture}(100,100)
\thicklines

\put(0,10){\line(0,1){20}}
\put(0,10){\line(4,-1){30}}
\put(30,2){\line(0,1){20}}
\put(0,30){\line(4,-1){30}}

\put(50,0){\line(4,1){30}}
\put(50,0){\line(0,1){20}}
\put(80,8){\line(0,1){20}}
\put(50,20){\line(4,1){30}}

\color{red}
\put(40,80){\circle*{3}}
\put(10,20){\circle*{3}}
\put(10,20){\vector(1,2){40}}

\put(50,5){\vector(2,1){30}}
\end{picture}
\end{center}

One way to try to find the point in the second image corresponding to the point in the first image, is called \textbf{sum of squared differences (SSD) minimization}. We take a small neighborhood of the point in question. We then search along the line in the second image for a neighborhood that minimizes the SSD. In other words, for two given neighborhoods of pixels, we calculate
\begin{center}
$\displaystyle \sum_{pixels} (($normalized left pixel$) - ($normalized right pixel$))^2$
\end{center}
and we search for the neighborhood in the second image that minimizes this sum.

Another problem can occur if parts of the subject are occluded, so that each camera's image contains some features that are not present in the other one. For example, assume the cameras are looking at a box with a red face and blue sides, on a black background. Both cameras see the red face and black background, but each camera sees only one of the blue sides. We might have the following two scanlines:
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
b & b & \color{blue} B & \color{red} R & \color{red} R & \color{red} R & b & b \\
\hline
\end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
b & b & \color{red} R & \color{red} R & \color{red} R & \color{blue} B & b & b \\
\hline
\end{tabular}
\end{center}
The question then arises, how do we decide to align these two scanlines? We could use a penalty function, e.g. assign a cost of 10 for each pixel removed for occlusion, and a cost of 20 for each poorly-matched pixel. The decision of which pixels to occlude can then be reduced to a simple path-finding algorithm.

\paragraph{Structure from Motion}

SFM involves inferring 3-dimensional structure from a moving camera taking 2-dimensional images. Much work has been done from the early 90s onward. In general, with $m$ camera images (the "motion") and $n$ points (the "structure"), we will have to solve an equation with $2mn$ constraints and $6m + 3n$ unknowns.

%===============================================================================

\part{Robotics I}

Robotics can be a difficult subject, because the environments are stochastic, partially observable, continuous, and may even be adversarial. A robot attempts to sense enough information to estimate an internal state that is sufficient to determine what to do next.

Assuming a simple robot moving on a two-dimensional plane, the robot will need the following state variables:
\begin{itemize_packed}
\item $x$, $y$: the position of the robot
\item $\theta$: the angular position (orientation)
\item $v$: the linear velocity
\item $\omega$: the angular velocity.
\end{itemize_packed}
These values can be updated using a simple approximation: for a small time step $\Delta t$, we calculate:
\begin{center}
\begin{tabular}{r@{} @{ }c@{ } @{}l}
$x'$ & $=$ & $x + v\Delta t \cos \theta$ \\
$y'$ & $=$ & $y + v\Delta t \sin \theta$ \\
$\theta'$ & $=$ & $\theta + \omega \Delta t$
\end{tabular}
\end{center}

\end{document}
